package bishi.meituan;

/**
 * @Classname Visit
 * @Description TODO
 * @Date 2021/9/11 20:04
 * @Created by ASUS
 */
public class Visit {
    boolean[][] visited;
    int cnt = 0;
    int[][] d = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int t_x = 0, t_y = 0;

    public int countPath(int[][] map, int x, int y) {
        visited = new boolean[map.length][map[0].length];
        int start_x = 0, start_y = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (map[i][j] == 1) {
                    start_x = i;
                    start_y = j;
                }
                if (map[i][j] == 2) {
                    t_x = i;
                    t_y = j;
                }
            }
        }
        dfs(map, start_x, start_y);
        return cnt;
    }

    private void dfs(int[][] map, int x, int y) {
        if (visited[x][y]) return;
        if (x == t_x && y == t_y) {
            cnt++;
            return;
        }
        if (map[x][y] == -1) return;
        visited[x][y] = true;
        for (int[] dirs : d) {
            int dx = x + dirs[0];
            int dy = y + dirs[1];
            if (dx < 0 || dx >= map.length) continue;
            if (dy < 0 || dy >= map[0].length) continue;
            dfs(map, dx, dy);
        }
        visited[x][y] = false;
    }

    public static void main(String[] args) {
        int[][] map = new int[][]{
                {-1, 1, 0, 0},
                {-1, -1, 0, 0},
                {0, 0,  2, 0}
        };
        System.out.println(new Visit().countPath(map, 3, 4));
    }
}
